package Elementary_algorithm.Tree;

import java.util.LinkedList;
import java.util.Queue;

/*
对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/data-structure-binary-tree/xoxzgv/
 */
public class _03对称二叉树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

        public boolean isSymmetric(TreeNode root) {
            return check(root, root);
        }

        //官解 BFS
        //BFS不是只能有一个顺序遍历
        //在有需要的时候，可以按照自己要求遍历
        //官解就是采用对称遍历将问题简单化
        public boolean check(TreeNode u, TreeNode v) {
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.offer(u.left);
            q.offer(v.right);
            while (!q.isEmpty()) {
                u = q.poll();
                v = q.poll();
                if (u == null && v == null) {
                    continue;
                }
                //u v 全为null的可能性已经消失了，如果运行到这步还有null，则必是u v 其中一个为null
                if ((u == null || v == null) || (u.val != v.val)) {
                    return false;
                }

                //采用对称遍历将问题简单化
                q.offer(u.left);
                q.offer(v.right);

                q.offer(u.right);
                q.offer(v.left);
            }
            return true;
        }

}
